package 力扣日常刷题.木22一月.第14天0123;

import java.util.Arrays;

/**
 * @author 帅小伙
 * @date 2022/1/23
 * @description (a, b)   (c,d)   构成递增的最大数
 */
public class Demo50动态规划中等最长数对链 {

    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
        int N = pairs.length;
        int[] dp = new int[N];
        Arrays.fill(dp, 1);

        // 从0开始到第j个元素的最大值
        for (int j = 1; j < N; ++j) {
            for (int i = 0; i < j; ++i) {
                if (pairs[i][1] < pairs[j][0])
                    dp[j] = Math.max(dp[j], dp[i] + 1);
            }
        }

        int ans = 0;
        for (int x : dp) if (x > ans) ans = x;
        return ans;
    }


}
